package 面试v1.字节;

public class Bm30 {

    private TreeNode index;

    public TreeNode Convert(TreeNode pRootOfTree) {
        if (pRootOfTree == null) {
            return null;
        }
        TreeNode ret = new TreeNode(-1);
        index = ret;
        dfs(pRootOfTree);
        TreeNode first = ret.right;
        first.left = null;
        return first;
    }

    private void dfs(TreeNode node) {
        if (node == null) {
            return;
        }

        TreeNode left = node.left;
        TreeNode right = node.right;
        dfs(left);
        index.right = node;
        node.left = index;
        index = node;
        dfs(right);
    }
}

class Bm30_1 {
    TreeNode pre=null;
    TreeNode root=null;
    public TreeNode Convert(TreeNode pRootOfTree) {
        if (pRootOfTree==null)
            return null;
        // 递归遍历左子树
        Convert(pRootOfTree.left);
        // 判断特殊情况
        if (root==null){
            root=pRootOfTree;
        }
        // 修改遍历的结点为双向链表
        if (pre!= null){
            pRootOfTree.left=pre;
            pre.right=pRootOfTree;
        }
        // 更新 pre
        pre=pRootOfTree;
        // 递归遍历右子树
        Convert(pRootOfTree.right);
        return root;
    }
}
